This notes are problem-centered: we introduce a problem and then the theory to efficiently solve it.
Use at Your Own Risk.
For each possible subarray we compute the sum and store the maximum
brute_force(a[])
n = a.length()
max = Integer.MIN_VALUE
for i = 0 to n
sum = 0
for j = i to n
sum += a[j]
if sum > max
max = sum
return max
Kadane's algorithm is based on two properties of the subarray with maximum sum:
To solve the problem we use Kadane's algorithm:
kadane_algorithm(a[])
n = a.length()
max = Integer.MIN_VALUE
sum = 0
for i = 0 to n
if sum > 0 // property 1)
sum += arr[i]
else // property 2)
sum = arr[i]
max = Math.max(sum, max)
return max
Given an array of size
We use the gauss sum to find the missing number:
actualSumsum = sum - acualSumGiven n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Traverse every array element and find the highest bars on the left and right sides.
Take the smaller of two heights.
The difference between the smaller height and the height of the current element is the amount of water that can be stored in this array element.
The point is to think locally, not globally.
We compute the left and right leaders.
An element of an array is a right leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader.
Left leaders are analogous.
Given the array
Now, how many units of water we can find on top of the cell
The minimum height between the left and right leader of the current position minus
Two Pointer Technique, more on this later.
The idea is taken from the Precomputation solution, where we only use two variables to store the currently "meaningful" leaders.
We take two pointers, left and right and we initialize left to 0 and right to the last index n-1.
We also create two variables, left_max and right_max, they represent the maximum left/right height seen so far.
Since left is the first left_max is 0, same for right_max.
This is intuitive: left_max of left = 0 falls outside the array, its height is 0, the same goes for right_max when right = n-1.
Now we iterate, as long as left < right.
We have to decide which pointer we have to shift: we shift the pointer that has smaller height value:
heights[left] < heights[right] we shift leftright otherwiseNow, if we have that heights[left] > left_max we can't store any water over the position pointed by left, it would fall as left_max is not high enough to contain any water over left
Otherwise we compute the amount of water stored in left, as always with left_max - heights[left]. Then we finally shift left by 1.
The reasoning with the right pointer is the same.
The following pseudo-code solves the problem
max_water(heights[])
n = heights.length()
result = 0
left = 0
right = n-1
left_max = 0 // max height seen by "left" so far
right_max = 0 // max height seen by "right" so far
while left < right
if heights[left] < heights[right] // shift "left"
if heights[left] > left_max
left_max = heigths[left] // cant store water
else
result += left_max - heights[left]
left += 1
else // shift right
if heights[right] > right_max
right_max = heights[right] // cant store water
else
result += right_max - heights[right]
right -= 1
return result
To solve this problem we use Binary Search.
We start by giving the basics of this technique.
An efficient algorithm that searches for a given key within a sorted array of items.
Binary search repeatedly divides the search range in half until the target element is found or the search range becomes empty, resulting in a time complexity of
Binary search is a technique that falls under the umbrella of the divide-and-conquer paradigm, that tackles a complex problem by breaking it down into smaller, more manageable subproblems of the same type:
Considering the binary search, we have:
It is also important to observe that when there are multiple occurrences of the searched key, the function returns the position of the first encountered occurrence, not necessarily the first occurrence in the vector.
However, it is often very useful to report the position of the first (or last) occurrence of the searched key.
We can obtain this behavior with the following pseudo-implementation.
binary_search(a[], target)
n = a.length()
low = 0
high = n - 1
answer = -1
while low < high
// (low + high)/2 might overflow if (high+low) is very big
middle = low + (high - low) / 2
if a[middle] == target
answer = middle
high = middle
else if a[middle] < target
low = middle
else
high = middle
return answer
In this implementation, when a match is found, we do not immediately return its position. Instead, we update the answer variable and set high to the position of this occurrence.
This way, we continue the search in the first half of the array, seeking additional occurrences of the key.
If there are more matches, answer will be further updated with smaller positions.
Consider a problem where all the possible candidate answers are restricted to a range of values between certain low and high possible answers.
In other words, any candidate answer [low, high].
We also have a boolean predicate pred defined on the candidate answers that tells us if an answer is good or bad for our aims.
Our goal is to find the largest good answer.
When no assumption are made about the predicate, we cannot do better than evaluating the predicate on all possible answers.
Hence, the number of times we evaluate the predicate is
On the other hand, if the predicate is monotone, we can binary search the answer to find it with
A predicate is said to be monotone if the truth value of a predicate is true for one combination of inputs, it will remain true if any of those inputs are increased (or remain the same). Similarly, if the truth value is false for one combination, it will remain false or become true if any of the inputs are increased (or remain the same).
The following pseudo-code clarifies the concept:
rangeBS(pred, low, high)
low = low;
high = high;
answer;
while low < high
mid = low + (high-low) / 2
if pred(mid) == true
answer = mid
low = mid + 1 // we want the largest good answer
else
high = mid
return answer
We can use the previous problem to compute the square root.
We are given a non-negative integer
The possible answers are in
We can find the result simply by doing rangeBS(p, 0, v+1)
We have a sequence of
If a certain distance is feasible (i.e., there exists a selection of points at that distance), then any smaller distance is also feasible.
Thus the feasibility is a monotone boolean predicate that we can use to binary search the answer.
As the candidate answers range from
What's the cost of evaluating the predicate?
We first sort the intervals.
Now we can evaluate any candidate distance
First we select the left extreme of the first interval as the first point.
Then, we move over the intervals and we choose greedily the first point, which is at a distance at least
Thus an evaluation of the predicate takes
The total running time is
Said Easy:
We want to place
Consider such a distance
The answers range is
We binary search it using rangeBS we have seen before, hence we evaluate the predicate
How much it costs to evaluate the predicate? We have to scan all the intervals checking that the passed candidate answers allow us to place at least
The pseudo-implementation greatly clarifies the process:
pred(intervals, distance, c)
// the first point is the start of the first interval
lastSelected = intervals[0].start
counter = 1
// for every interval in intervals
for i in intervals
// we select as many points as we can in every interval
while Math.max(lastSelected + distance, i.start) <= i.end
lastSelected = Math.max(lastSelected + distance, i.start)
counter++
return counter >= c
socialDistancing(intervals, c)
// l is the maximum length of an interval
if l < c
return -1 // there is no solution
// sort the intervals by the start
intervals.sort()
rangeBS(1, l+1, pred)
We can use the binary search philosophy to solve the problem.
We compute the middle of the array.
If the element in the middle is smaller than its right neighbor than the right neighbor could be a peak, and we do low = mid + 1 to proceed the search in the right side of the array.
Otherwise we do the opposite.
peak_elements(a[])
n = a.length()
low = 0
high = n - 1
while low < high
mid = low + (high - low) / 2
if a[mid] < a[mid + 1]
low = mid + 1
else
high = mid
return low
This solution works because a peak is guaranteed to be found (as a last resource, in the first or last element of the array).
The beauty of this solution is that it naturally covers all the strange cases.
It would be tempting to write something like
if a[mid] > a[mid+1] && a[mid] > a[mid-1]
return mid
but that requires to cover many edge cases (array of size 1, 2, if mid is
Find the maximum possible sum from one leaf node to another.
To solve this problem we need to use a tree traversal.
Fist we go back and give the basics.
Tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once.
Such traversals are classified by the order in which the nodes are visited.
Traversing a tree involves iterating over all nodes in some manner.
Because from a given node there is more than one possible next node some nodes must be deferred, aka stored, in some way for later visiting.
This is often done via a stack (LIFO) or queue (FIFO).
As a tree is a recursively defined data structure, traversal can be defined by recursion.
In these cases the deferred nodes are stored implicitly in the call stack.
Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue.
In depth-first search (DFS), the search tree is deepened as much as possible before going to the next sibling.
To traverse binary trees with depth-first search, perform the following operations at each node:
The choice of exactly one color determines exactly one visit of a node as described below.
Complexity Analysis:
The preorder traversal is a topologically sorted one, because the parent node is processed before any of its child nodes is done.
procedure postorder(node)
if node = null
return
postorder(node.left)
postorder(node.right)
visit(node)
In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.
A simple solution is to traverse the tree and do following for every traversed node
Given a Binary Tree, find the maximum sum path from a leaf to root.
For example, in the following tree, there are three leaf to root paths:
The sums of these three paths are 16, 4 and 17 respectively.
The maximum of them is 17 and the path for maximum is 7 -> 10.
10
/ \
-2 7
/ \
8 -4
Solution:
Here we provide a Java pseudo-implementation of the problem:
maxValue = 0
targetLeaf = null
maxLeafRootSum(root)
targetLeaf = findTargetLeaf(root, 0)
print(maxValue)
// set targetLeaf to the leaf with maximum sum path to root
findTargetLeaf(node, currMaxValue)
if root == null
return
// hold the sum of nodes on path from root to this node
currMaxValue += node.value
// leaf and the path to this has maximum sum: set targetLeaf
if node.isLeaf
if currMaxValue > maxValue
maxValue = currMaxValue
targetLeaf = node
// this is not a leaf node: recur down to find targetLeaf
findTargetLeaf(node.left, currMaxValue)
findTargetLeaf(node.right, currMaxValue)
So, the trivial solution of Maximum Path Sum works as follows:
For every node we call twice maxLeafRootSum, which costs O(n), hence the total cost is
We can find the maximum sum using single traversal of binary tree.
The idea is to maintain two values in recursive calls
For every visited node
As before, here a pseudo-code implementation:
maxValue = 0
// calculates two things:
// 1) maximum path sum between two leaves, which is stored in maxValue.
// 2) root-to-leaf path sum, which is returned.
maxPathSum(root)
if root == null
return 0
left = maxPathSum(root.left)
right = maxPathSum(root.right)
maxValue = Math.max(maxValue, left + right + root.value)
return left + right + root.value
In "one pass" (aka one traversal) we do what we did in the trivial solution.
The reasoning is the following:
The result is maxValue when the program terminates.
Said Easy:
To solve the problem we use a custom post-order visit maxPathSum that exploits a global variable maxSum to store the result.
Our visit maxSumPath receive in input the root of the tree and then
null we return left = maxSumPath(root.leftST), we recur on the left subtreeright = maxSumPath(root.rightST), we recur on the right subtreeleft is the sum from the current node to a leaf in the left subtree, analogous for rightmaxSum = max(left+right+root.value, maxValue), update the maxSum if we found a bigger path from leaf to leaf passing for the current nodeWhen the visit terminates the result is stored in the global variable maxSum
Given a sorted array
The naive approach is obvious and takes O(n^2), we simply scan the array and we return when we find two numbers that adds up to X.
existsPairSum(a[], x)
n = a.length()
for i = 0 to n
for j = i+1 to n
if a[i] + a[j] == x
return true
if a[i] + a[j] > x
break // a is sorted, need a new "i"
return false
Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array.
It employs using two pointer, typically one from the start of the array going left-to-right and one from the end of the array going right-to-left, until they meet.
We already seen a sneak peak of this in Trapping Rain Water.
We take two pointers, one representing the first element and other representing the last element of the array, and then we add the values kept at both the pointers.
If their sum is smaller than X then we shift the left pointer to right or if their sum is greater than X then we shift the right pointer to left, in order to get closer to the sum.
We keep moving the pointers until we get the sum as X.
existsPairSum(a[], x)
n = a.length()
left = 0
right = n-1
while left < right
if a[left] + a[right] == x
return true
if a[left] + a[right] < x
left += 1 // smaller than target, we need to increase
else
right -= 1 // bigger than target, we need to decrease
return false
There are
For each frog two values
For each mosquito two values are known
Frogs and mosquitoes are represented as points on the coordinate axis.
The frog can eat mosquito if mosquito is in the same position with the frog or to the right, and the distance between them is not greater than the length of the tongue of the frog.
If at some moment several frogs can eat a mosquito the leftmost frog will eat it (with minimal
After eating a mosquito the length of the tongue of a frog increases with the value of the size of eaten mosquito.
It's possible that after it the frog will be able to eat some other mosquitoes (the frog should eat them in this case).
For each frog print two values - the number of eaten mosquitoes and the length of the tongue after landing all mosquitoes and after eating all possible mosquitoes by frogs.
Each mosquito is landing to the coordinate axis only after frogs eat all possible mosquitoes landed before.
Mosquitoes are given in order of their landing to the coordinate axis.
A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
The time complexity of operations on the binary search tree is linear with respect to the height of the tree.
Binary search trees allow binary search for fast lookup, addition, and removal of data items.
Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm.
The complexity analysis of BST shows that, on average, the insert, delete and search takes
In the worst case, they degrade to that of a singly linked list:
Searching for a specific key can be programmed recursively or iteratively.
Searching begins by examining the root node. If the tree is nil, the key being searched for does not exist in the tree.
Otherwise, if the key equals that of the root, the search is successful and the node is returned.
If the key is less than that of the root, the search proceeds by examining the left subtree. Similarly, if the key is greater than that of the root, the search proceeds by examining the right subtree.
This process is repeated until the key is found or the remaining subtree is nil.
If the searched key is not found after a nil subtree is reached, then the key is not present in the tree.
For certain operations, given a node
Assuming all the keys of the BST are distinct, the successor of a node
On the other hand, the predecessor of a node
Following is pseudo-code for finding the successor and predecessor of a node
Removing an element from a BST costs
We store the position of the frogs in a BST, frogBST.
When a mosquito lands on a position rogBST.predecessor(b) query on the tree.
It is possible that some mosquito cannot be eaten right away, the uneaten mosquitoes will be stored in their own BST (mosquitoBST), using their landing position as keys.
We have to handle overlaps.
If a frog partially overlaps with another then we have to fix the overlap to make sure that thy cover different ranges.
If a frog totally overlaps with another then the second frog will never eat and must be removed.
To solve the overlapping that may arise within the input:
f1 partially overlaps the frog f2 move f2 by adding to its position the needed amount. Mind that f2 has now a shorter tongue (shorted by the amount of the shift)f1 fully overlaps f2, remove f2The algorithm behaves as follows:
frogBST using their position as keyf of m in frogBST, if f.position + f.tongue >= m.positionf eats the mosquito m and its tongue grows by the size of mf now can eat other mosquitoes that could not be eaten before, inspect mosquitoBST to see if there is a mosquito that f can eat, and in case repeat.m' of f.position in mosquitoBST and see if f.position + f.tongue >= m'.positionf now may overlap or fully contain other frogsfrogBST:f.position + f.tongue + 1f then delete this frog as it will never eatmosquitoBST and continueGiven an array A[0, n-1] and an integer k, the goal is to find the maximum of each subarray (window) of A of size k.
The simplest approach is to consider each of the
Within each window we compute its maximum by scanning the window through all its elements, which takes
We then have that this brute force approach takes
The problem in this approach is that when we compute the maximum of the current window we disregard all the previous computations, done on windows that are partially overlapping to the current one.
To solve more efficiently the problem we need a data structure that handle the next window while capitalizing on the progress made in processing the preceding window.
We consider the two following observations:
We then require a data structure capable of performing three crucial operations on a (multi)set:
A Balanced Binary Search Tree (BBST) supports any of these operations in
This way we can solve the problem in
The algorithm at this point is easy:
In rust we use BTreeSet that offers efficiently the operations insert, remove, and last(find max).
The only hiccup is that it do not store repeated elements, hence we store elements as pair with their index in the array.
A heap is a tree-based data structure that satisfies the heap property:
C, if P is a parent node of C, then the key of P is greater than or equal to the key of C.P is less than or equal to the key of CThe main operations are:
The heap-based solution is theoretically less efficient than the BST one (
Since we are talking about the maximum the immediate choice is a priority queue with its most famous manifestation being the (max-)heap.
A max-heap stores a set of
pushpeekpopWe can solve the sliding window maximum property by employing a max-heap and scanning the array from left to right:
With this approach there are a total of
Since the maximum number of elements present in the heap at any given time is up to
Consequently the overall time complexity is
heamSWM(a[])
n = a.length()
MaxHeap h
maxs[n-k+1]
for i = 0 to k
h.push((a[i], i))
for i = k to n
h.push((a[i], i))
while !h.isEmpty()
if h.peek().i < i-(k-1) // max ouside of the window
h.pop()
else
break
maxs.push(h.peek())
return maxs
The BST solution can do more than what is strictly necessary, e.g. what is the second largest element in the window?
The fact that we can do much more than what is requested, it’s an important signal to think that a faster solution could exist.
The better solution uses a deque a double-ended queue, which supports constant time insertion, removal and access at the frond and back of the queue.
There are many ways to implement a deque, the simplest one (but not the fastest) is a bidirectional list.
The algorithm starts with an empty deque
That is, the window starts before the beginning of a.
Then we start sliding the window one position at a time and remove/insert elements from
The element in front of the deque will be the element to report.
More precisely, we repeat
Note: the deque stores indices, not actual elements.
// q = [a1, ..., ak]
// back front
// tail head
slidingWindowMaximum(a[])
n = a.length()
Deque q
maxs[n-k+1]
for i = 0 to k
while !q.isEmpty() && a[i] > a[q.back()]
q.popBack()
q.pushBack(i)
maxs.push(a[q.front()]);
for i = k to n
// remove elements that dont belongs in the window
while !q.isEmpty() && q.front() + k <= i
q.popFront()
// remove elements that are smaller that the current element
// as this elements cannot be the maximum for this window nor
// for future windows
while !q.isEmpty() && a[i] > a[q.back()]
q.popBack()
q.pushBack(i)
maxs.push(a[q.front()])
return maxs;
Said Easy:
Theorem: The elements in
Proof: we prove the theorem by induction on the number of iterations
a[i+1] as the tail of the queue just below the first element which is larger than it (if any). Thus the queue remains sortedNow we introduce the definition of right leaders of the window to show that the largest element within the current window is at the top of the queue.
Given a window, an element is called a right leader if and only if the element is larger that any other element of the window at its right.
As an example consider the following image, where the red elements are right leaders:
Theorem: At every iteration
Proof:
We derive the correctness of the algorithm by combining the sortedness of Q with the fact that the largest right leader is the element to report.
We have a loop that is repeated n times.
The cost of an iteration is dominated by the cost (and thus the number) of pop operations.
However in a certain iteration we may pop out all the elements in the deque.
As far as we know there may be up to n elements in the deque and thus an iteration costs
Thus we get that the cost of the algorithm is
The problem here list in this kind of complexity analysis.
There may indeed exists very costly iterations but they are greatly amortized by many very cheap ones.
Overall, the number of pop operations cannot be larger than
Each of them cost constant time and thus the algorithm runs in linear time.
Given an array A[0..n-1] having distinct elements, the goal is to find the next greater element for each element of the array in order of their appearance in the array.
Adapt the Sliding Window Maximum Solution.
TODO
Consider a set of
We say that two intervals
Compute the maximum number of overlapping intervals.
Example:
We have a set of 10 intervals, the maximum number of overlapping intervals is 5 (at positions 3 and 4)
The Sweep Line Algorithm is an algorithmic paradigm used to solve a lot of problems in computational geometry efficiently.
The sweep line algorithm can be used to solve problems on a line or on a plane.
The sweep and line algorithm use an imaginary vertical line sweeping over the x-axis.
As it progresses, we maintain a running solution to the problem at hand.
The solution is updated when the vertical line reaches a certain key points where some event happen. The type of the event tells us how to update the solution.
Let's apply the sweep and line algorithm to the problem above.
We let the sweep line from left to right and stop at the beginning or at the end of every interval.
These are the important points at which an event occurs: interval start or end.
We also maintain a counter which keeps track of the number of intervals that are currently intersecting the sweep line, along with the maximum value reached by the counter so far.
For each point: we first add to the counter the number of intervals that begin at that point, and then we subtract the number of intervals that end at that point.
The figure below shows the points touched by the sweep line and the values of the counter:
Observation: The sweep line only touches points on the x-axis where an event occurs.
This is important because the number of considered points, and thus the time complexity, is proportional to the number of intervals, and not to the size of the x-axis.
In Practice:
We create an array axis of pairs (p, isStart), where
p is either a isStart is true if p is a Then we sort axis by the first element of each pair, and we set counter = 0 and max = 0.
Now we iterate over axis:
axis[i] is the start of an interval (i.e., `axis[i].isStart == true)counter++max = Math.max(counter, max)counter--Let’s tackle a second problem to apply the sweep line paradigm to a two-dimensional problem.
We are given a set of
The goal is to find the closest pair of points in the set.
The distance between two points
Let's now use the sweep-line technique.
We start by sorting the points in increasing order of their
We keep track of the shortest distance, denoted with
Initially we set
Then we use a vertical sweep line to iterate through the points, attempting to improve the current shortest distance
Consider the point
We can improve
If such point exists it must have a
The following figure shows the rectangle within this point must lie.
There can be at most 6 points within this rectangle.
The 6 circles within the perimeter of the rectangle represent points that are at distance exactly
Four our purpose a slightly weaker result is enough, which states that the rectangle contains at most 8 points.
To understand why consider the 8 squares in the figure above.
Each of these squares, including its perimeter can contain at most one point.
Assume, for sake of contradiction, that a square contains two points, denoted as
The distance between
However this is not possible, because otherwise the value of
Let's use the above intuition to solve the problem.
We maintain a BST with points sorted by their
When processing a point
If the current point has an
Otherwise we compute its distance with
Before moving the sweep line to the next point, we insert
What is the complexity of the algorithm?
Clarification: To store the solution we use a set. This set stores all the points at the (current) minimum distance
When the program terminates we extract two random points from the set.
In rust:
BTreeSet ordering by the second componentThe following is the intuitive solution.
It has two nested loops, one that iterates right-left times and the inner one that iterates
The complexity then is
isCovered(ranges, left, right)
for i = left to right
covered = false // i is not covered until proven otherwise
for range in ranges
if i >= range.start && i <= range.end
covered = true // i is covered by the current interval
break;
// if i is not covered then we return false
if covered == false
return false
// each i in [left, right] is covered by at least one range
return true;
To solve the problem more efficiently we use sweep line and a map.
The complexity is linear in the maximum between the number of ranges and right
isCovered(ranges, left, right)
// map: point i -> number of open ranges in i
HashMap openRangesAt;
for range in ranges
openRangesAt.insert(openRangesAt.getOrDefault(range.start, 0) + 1)
// range.end+1 as the ranges are inclusive!
openRangesAt.insert(openRangesAt.getOrDefault(range.end+1, 0) - 1)
openRangesNow = 0
for i = 0 to left
openRangesNow += openRangesNow.getOrDefault(i, 0)
for point=left to right
openRangesNow += openRangesNow.getOrDefault(point, 0)
if openRangesNow == 0
return false
return true
The array
Let's call the sequence of one or more consecutive elements in
Also let's call the segment
Note: if the distance between two numbers is abs(1) then the two numbers are consecutive.
Find any longest k-good segment.
Note: we return the indexes of the longest k-good segment
This problem is somewhat similar to Sliding Window Maximum.
There you wanted to know the maximum element for every window of size
Here we want to have the longest window with exactly
We then use the two-pointers trick to basically simulate a dynamic sliding window.
The algorithm behaves as follows:
unique to store the distinct elementsleft and right both starts at right becomes rightunique of size at most a[right] in uniqueunique is still of size at most unique.size() <= k) (the inserted element either was new but there were less than unique) AND the current size of the window is the biggest so far?left and right as they might be the delimiters of the resultunique.remove(a[left])left++findMaxSegment(a[], k)
n = a.length
left = 0, right = 0 // delimiter of the current window
maxLeft = 0, maxRight = 0 // delimiter of the current result
currentSize = 0
maxSize = -1
Set unique
while right < n
if uniqueSet.size() <= k
unique.add(a[right])
currentSize++
if uniqueSet() <= k && currentSize > maxSize
maxLeft = left
maxRight = right
maxSize = currentSize
right++
else
unique.remove(a[left])
left++
return (maxLeft, maxRight)
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
kNote that:
x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.The obvious brute force approach: from each element we compute every possible subarray starting in that element, check if sum is a multiple of k and store the maximum length so far.
Prefix sums, also known as cumulative sums or cumulative frequencies, offer an elegant and efficient way to solve a wide range of problems that involve querying cumulative information about a sequence of values or elements.
The essence of prefix sums lies in transforming a given array of values into another array, where each element at a given index represents the cumulative sum of all preceding elements in the original array.
An example of prefix sum array is shown in the picture:
Where it is clear that
We can use the combinator scan to produce the prefix sums from an iterator.
scan is an iterator adapter, it maintains an internal state, initially set to a seed value, which is modified by a closure taking both the current internal state and the current element from the iterator into account.
let a = vec![2, 4, 1, 7, 3, 0, 4, 2];
let psums = a
.iter()
.scan(0, |sum, e| {
*sum += e;
Some(*sum)
})
.collect::<Vec<_>>();
assert!(psums.eq(&vec![2, 6, 7, 14, 17, 17, 21, 23]));
We have a string
Each query
Let's consider an example (remember that we use 1-indexing)
The idea is that of computing the binary vector
This way the answer to the query
We are given an array
The goal is to permute the elements in
The key is to observe that if we want to maximize the sum we have to assign the largest value to the most frequently accessed entries.
Thus the solution consists of sorting both
Therefore, once we have computed the frequencies, the solution takes
We are left with the problem of computing access frequencies.
We want to compute an array
Computing this array by updating every single entry
We use the prefix sum to solve the problem.
We construct an array
Interestingly we need to modify just two entries of
Initially we set all entries of
Then for a query
Therefore, the prefix sum of
This algorithm takes
The following pseudo-implementation clarifies the approach:
littleGirlMax(a[], q[])
n = a.length()
u[n]
for (l, r) in q
u[l]++
if r + 1 < n
u[r+1]--
f[n]
pS = 0
for i = 0 to n
pS += u[i]
f[i] = pS
a.sortDecreasing()
f.sortDecreasing()
res = 0
for i = 0 to n
res += a[i] * f[i]
return res
Basically we permute the elements of
Given an array
Formally, you need to find the number of such pairs of indices
If
We compute an array
Remember: suffixes are fixed portions,
Then we scan
Every time the prefix sum at position
This is because the part
Since the values in
Clarification:
Indeed if one of this suffix sums to
The solution is based on the following mathematical property:
Observation: any two prefix sums that are not next to each other with the same mod k, or a prefix sum with mod k = 0 that is not the first number will yield a valid subarray.
checkSubarraySum(array, k)
n = array.length()
prefixSumArray[] // prefix sum array
pS = 0
for i = 0 to n
pS += array[i]
prefixSumArray[i] = pS
// map: modulo -> index i st prefixSumArray[i] % k = modulo
HashMap modsToIndices
for (i, prefixSum) in prefixSumArray.enumerate()
modulo = prefixSum % k
if modulo == 0 && i != 0 // if modulo is 0 and not the first ok
return true
// first time we see this modulo
if modsToIndices.contains(modulo) == false
modsToIndices.insert(modulo, i)
else
// this modulo has been seen
previousIndex = modsToIndices.get(modulo);
if previousIndex < i - 1
return true
return false
Observation:
We really do not need a full prefix sum array, it is enough to compute sum as we go and use it also as the mod result (we make sum = sum%k and use it as key, sums in modulo works). This is true because we never use the prefix sum of an element before the predecessor, so we can store only the sum up until now.
You have an array
You need to do a number of update operations on it.
In each update you specify l, r and val which are the starting index, ending index and value to be added.
After each update, you add the val to all elements from index l to r.
After u updates are over, there will be q queries each containing an index for which you have to print the element at that index.
Basically we have to support two operations:
access(i), which returns range_update(l,r,v), which update the entries in To efficiently solve this problem we introduce a new data structure, the Fenwick Tree
The Fenwick Tree, also known as the Binary Indexed Tree (BIT), is a data structure that maintains the prefix sums of a dynamic array.
With this data structure we can update values in the original array and still answer prefix sum queries, both in logarithmic time.
Consider the following problem: we have an array A[1..n] of integers and we would like to support the following operations:
sum(i) returns the sum of the elements in A[1...i]add(i,v) adds the value v to the entry A[i]We have two trivial solutions:
A as it is. This way, sum(i) is solved by scanning the array in add(i,v) is solved in A. This way sum(i) is solved in add(i,v) is solved modifying all the entries from i to n in The sum/add query time trade-offs of these solutions are unsatisfactory
The Fenwick Tree provides better tradeoffs for this problem.
The Fenwick tree efficiently handles these queries in
In fact the Fenwick tree is an implicit data structure, which means it requires only A
In our description, we will gradually introduce this data structure by constructing it level by level.
We use the following 1-indexed array in our example:
We start with a simpler version of the problem: we focus on solving sum queries only for positions that are powers of 2, positions 1, 2, 4, 8 in A.
The solution of this simplified version, shown in the picture, will be the first level of the Fenwick Tree
We notice that:
AWith this solution we have that:
sum(i) query: straightforward, we simply access the node i, provided that i is a power of 2add(i,v) query: we need to add v to all the nodes that covers ranges that include the position i, for example if we want to do add(3,10) we need to add 10 to the nodes 4 (as it has range add(i,v): find the smallest power of 2 grater than i, let's call it j, and we add v to the nodes j, j*2, j*(2^2), ... (j is the index in the original array, stored over every node in the picture above)We observe that sum takes constant time and add takes
This is very good, can we extend this solution to support sum queries on more positions?
Observation: currently we are not supporting queries for positions within the ranges between consecutive powers of 2.
Look at the image above: positions that falls in the range (subarray) [5, 7], which falls between the indices
In fact we can't make the query sum(5).
Enabling queries for this subarray is a smaller instance of our original problem.
We can apply the same strategy by adding a new level to our tree.
The children of a node stores the partial sums starting from the next element.
The emphasis is in starting.
If the subarray is A[l..r], the new level will support the sum(i) query for any i such that i-l+1 is a power of 2.
Lemma: our two-level tree can now handle sum(i) queries for positions that are the sum of two powers of 2.
Proof:
i expressed as i at the second levelsum(5)Which are the position still not supported? The positions that are neither a power of 2 or the sum of two powers of 2.
In our example, we can't compute sum(7) as 7 is either of those.
To support this we add a new level to our tree, so we can support positions that are sum of three powers of 2
Example: intuition on how to compute sum(7)
sum(7)And we are done, this is the Fenwick tree of the array A.
We can make some observations:
A because any of its entries A[i] can be simply obtained by doing sum(i) - sum(i-1). This is why the Fenwick tree is an implicit data structureNow, let’s delve into the details of how to solve our sum and add queries on a Fenwick tree.
sum queryThis query involves beginning at a node i and traversing up the tree to reach the node 0. Thus sum(i) takes time proportional to the height of the tree, resulting in a time complexity of
Let's consider the case sum(7) more carefully.
We start at node with index 7 and move to its parent (node with index 6), its grandparent (node with index 4), and stop at its great-grandparent (the dummy root 0), summing their values along the way.
This works because the ranges of these nodes (
Answering a sum query is straightforward if we are allowed to store the tree's structure.
However a significant part of the Fenwick tree's elegance lies in the fact that storing the tree is not actually necessary.
This is because we can efficiently navigate from a node to its parent using a few bit-tricks, which is the reason why the Fenwick trees are also called Binary Indexed Trees.
We want to compute the parent of a node, and we want to do it quickly and without representing the structure of the tree.
Let's consider the binary representation of the indexes involved in the query sum(7)
Theorem: the binary representation of a node's parent can be obtained by removing the trailing one (i.e., the rightmost bit set to 1) from the binary representation of the node itself.
addNow we consider the operation add(i,v).
We need to add the value v to each node whose range include the position i.
Surely, the node i itself is one of these nodes as its range ends in i.
Additionally, the right siblings of node i also encompasses the position i in their ranges.
This is because siblings share the same starting positions, and right siblings have increasing sizes.
The right siblings of the parent node of i, the right siblings of the grandparent, and so on can also contain position i.
It might seem like we have to modify a large number of nodes, however we can show that the number of nodes to be modified is at most log(n).
This is because each time we move from a node to its right sibling or to the right sibling of its parent, the size of the covered range at least doubles. And a range cannot double more than \log(n) times.
If we want to perform add(5, x) we just need to modify the nodes in red:
We now know which are the nodes to modify for add(i, x).
Let's discuss how to compute these nodes with bit-tricks.
Continuing the above example, starting with i = 5, the next node to modify is its right sibling, node 6.
Their binary representation is
We see that if we isolate the trailing one in the binary rep. of 5, which is 0001, and add it to the binary rep. of 5 itself, we obtain the binary rep of 6.
Finding the Sibling
The binary representation of a node and its sibling matches, except for the position of the trailing one. When we move from a node to its right sibling, this trailing one shifts one position to the left.
Adding this trailing one to a node accomplishes the required shift.
Now, consider the ID of a node that is the last child of its parent.
In this case, the rightmost and second trailing one are adjacent. To obtain the right sibling of its parent, we need to remove the trailing one and shift the second trailing one one position to the left.
Thankfully, this effect is one again achieved by adding the trailing one to the node’s ID.
The time complexity of add is
The following is a minimal implementation
While we’ve transitioned to 0-based indexing for queries, internally, we still use the 1-based indexing to maintain consistency with the examples above.
#[derive(Debug)]
pub struct FenwickTree {
tree: Vec<i64>,
}
impl FenwickTree {
pub fn with_len(n: usize) -> Self {
Self {
tree: vec![0; n + 1],
}
}
pub fn len(&self) -> usize {
self.tree.len() - 1
}
/// Indexing is 0-based, even if internally we use 1-based indexing
pub fn add(&mut self, i: usize, delta: i64) {
let mut i = i + 1;
assert!(i < self.tree.len());
while i < self.tree.len() {
self.tree[i] += delta;
i = Self::next_sibling(i);
}
}
/// Indexing is 0-based, even if internally we use 1-based indexing
pub fn sum(&self, i: usize) -> i64 {
let mut i = i + 1;
assert!(i < self.tree.len());
let mut sum = 0;
while i != 0 {
sum += self.tree[i];
i = Self::parent(i);
}
sum
}
pub fn range_sum(&self, l: usize, r: usize) -> i64 {
self.sum(r) - if l == 0 { 0 } else { self.sum(l - 1) }
}
fn isolate_trailing_one(i: usize) -> usize {
if i == 0 {
0
} else {
1 << i.trailing_zeros()
}
}
fn parent(i: usize) -> usize {
i - Self::isolate_trailing_one(i)
}
fn next_sibling(i: usize) -> usize {
i + Self::isolate_trailing_one(i)
}
}
We are given an array
The goal is to count the number of inversions of
We assume that the largest integer
This assumption is important because we're using a Fenwick Tree of size
If, on the other hand,
If elements are equal than they have the same rank.
rank goes from
The algorithm behaves as follow:**
a is empty, there are no inversions, so the function returns 0.ft with length of max + 1, where max is the maximum value in the array a. This is done to efficiently compute cumulative sums.e in the input array ae that appear later in the array (e + 1) and max. Since the Fenwick Tree stores cumulative sums, this effectively gives the count of elements greater than e encountered so far.e appears at position i: the elements that appears at position j with j > i and such that a[j] > e are inversionsi < j and a[j] > a[i]e in the Fenwick Tree using the add method. This step is crucial for accurately counting inversions since we need to keep track of how many times each element appears in the array.count.In this particular use case, the Fenwick Tree is used to efficiently calculate the cumulative sum of elements greater than the current element encountered so far.
This is crucial for determining the count of inversions.
The range_sum method computes the cumulative sum efficiently by exploiting the tree structure, resulting in an overall time complexity of n is the size of the input array a.
Consider the following pseudo-implementation:
countInversions(a[])
n = a.length()
max = a.max()
// use the implementation presented above!
ft = FenwickTree.withLen(max + 1)
counter = 0
for i = 0 to n
counter += ft.rangeSum((a[i]+1), max)
ft.add(a[i], 1)
return counter
We are given an array A[1,n] initially set to 0.
We want to support two operations:
access(i) returns the element range_update(l, r, v), updates the entries in A[l,r] adding to them vThe following Fenwick solution solve the problem
A we build the Fenwick Tree of length n (mind that A is initialized with all zeros)access(i) is a wrapper of the operation sum(i) we have seen before range_update(l,r,v) exploit the operation add(i, v) of the implementation of the Fenwick Tree:l is <= than r, aka that the interval of entries to update is well formedr <= n, aka that the interval of entries to update is actually in the arrayadd(l,v): this trigger the addition of the value v to each node whose range include the position l in the Fenwick Treeadd(r, -v): this trigger the subtraction of the value v to each node whose range include the position r in the Fenwick Treev in the Fenwick tree, this means that prefix sum are coherent and the elements in [l,r] are increased by vsum(i) we have written in the implementation of the FT results in the access operation in this problem (sum(i) == access(i)) by the construction of range update.
Example: consider the empty FT (as an array):
range_update(1,2,2), we obtain:[0,2,0,-2][0,2,2,0]access(2), we want the third element of the arraysum(2) is the prefix sum of the elements The solution of the problem is given by the following data structure:
#[derive(Debug)]
struct UpdateArray {
ft: FenwickTree,
}
impl UpdateArray {
pub fn with_len(n: usize) -> Self {
Self {
ft: FenwickTree::with_len(n),
}
}
pub fn len(&self) -> usize {
self.ft.len()
}
pub fn access(&self, i: usize) -> i64 {
self.ft.sum(i)
}
pub fn range_update(&mut self, l: usize, r: usize, v: i64) {
assert!(l <= r);
assert!(r < self.ft.len());
self.ft.add(l, v);
if r + 1 < self.ft.len() {
self.ft.add(r + 1, -v);
}
}
}
The range update of the previous problem is paired with the access(i) operation.
Here we want to support:
range_update(l, r, v), same as beforesum(i), returns As before, we notice that
add(i,v) provided by the basic implementation of our FT is a special case of range_update, more specifically add(i,v) == range_update(i, n, v) where n is the size of the treeaccess(i) is still being supported using sum(i) - sum(i-1)The difference between this and Update the Array is that here we have to support sum, while we where only supporting access(i) in Update the Array.
Let's say that we use here the same approach we used in Update the Array.
For range_update(l,r,v) we modify the Fenwick Tree by adding
range_update(1,2,2)[0,2,2,0]range_update, we have sum(2), it should be More formally: consider range_update(l,r,v) on a brand new FT (all zeroes).
The correct result of a sum(i) after the range_update is:
sum(i) is sum(i) is sum(i) is Instead the results returned by our implementation of sum(i) are the following:
sum(i) is sum(i) is sum(i) is Those counts are correct, if you instance them in an example they work.
To fix those problems we employ another Fenwick Tree, FT2, which will keep track of these discrepancies.
When we perform a range_update(l,r,v) we:
ft1.add(l,v)ft1.add(r+1,-v)ft2.add(l, -v*(l-1))ft2.add(r+1, v*r)This revised approach ensures that the result of sum(i) can be expressed as
sum(i) in the first fenwick treeAnd we get
sum(i)
// a i b
ft1.sum(i) * i + ft2.sum(i)
The value of
We are given
There are no coinciding endpoints among the segments.
The task is to determine and report the number of other segments each segment contains.
Alternatively said: for the segment
We provide two solutions to this problem:
We use a sweep line & Fenwick tree approach.
We build an array events where every entry is [l_i, r_i, i], and then we sort events by start of the respective range, l_i.
Then we build the Fenwick tree with size
Now we scan the events again.
When we process the event
To find the solution of this problem for the current segment (aka the number of segments contained in the current one) we need to know the number of the segments that starts after the current one that also end before the current one, before
This is computed with a query sum(r_i - 1) on the Fenwick Tree.
Why sum(r_i - 1) is the number of segments contained in
Because all the segments that starts before
Therefore sum(r_i - 1) is the number of segments that starts after
After computing the solution for the current segment we subtract
This is why the segments that starts before the current one but overlaps with it are not counted.
The following snippet implement the solution above, using the Fenwick tree previously defined.
nestedSegmentFT(segments[])
n = segments.length()
List result
List events
for (i, segment) in segments.enumerate()
events.push((segment.start, segment.end, i))
// sort by the first component of each element, s_i
events.sort()
tree = FenwickTree(2*n + 1)
for event in events
tree.add(event.end, 1)
for event in events
result.push((tree.sum(event.end - 1), event.index))
tree.add(event.end, -1)
// sort by the second element, the index, to
// restore the original ordering of segments
result.sort()
return result
A Segment Tree is a data structure that stores information about array intervals as a tree.
This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array.
The key point here is range queries, not only range sums!
We can find the sum of consecutive array elementsA[l..r] or find the minimum element in a segment in
Between answering such queries we can modifying the elements by replacing one element of the array, or even changing the elements of a whole subsegment (e.g., assigning all elements a[l..r] to any value, or adding a value to all element in the subsegment)
Segment trees can be generalized to larger dimensions. For instance, with 2-dimensional Segment trees you can answer sum or minimum queries over some subrectangle of a given matrix in
We consider the simplest form of Segment Trees.
We want to answer sum queries efficiently.
The formal definition of our task is the following: given an array
Observation: even our simple form of Segment Tree is an improvement over the simpler approaches:
We can take a divide-and-conquer approach when it comes to array segments.
We compute and store the sum of the elements of the whole array, i.e. the sum of the segment
Then we split the array into two halves
We can view this segment as forming a binary tree: the root is the whole array segment, and each vertex (except leaves) has exactly two children.
This is why this data structure is called "segment tree".
Example: consider the array
From the short description we just gave we can conclude that Segment Trees only require a linear number of vertices.
The first level of our tree contains a single node (the root), the second level will contain two nodes, the third we have four nodes, until the reaches
Thus, the number of vertices in the worst case can be estimated by the sum
The height of a Segment Tree is
Before constructing the segment tree we need to decide:
Note that a vertex is a leaf if its corresponding segment covers only one value of the original array. It is present at the lowest level of the tree and its value would be equal to the corresponding element
For construction of the segment tree, we start at the bottom level (the leaves) and assign them their respective values.
On the basis of these values we can compute the values of the previous level, using the merge function.
And on the basis of those, we can compute the values of the previous, and so on until we reach the root.
It is convenient to describe this operation recursively in the other direction, i.e., from the root vertex to the leaf vertices.
The construction procedure, if called of a non-leaf vertex, does the following:
We start the construction at the root vertex, and hence, we are able to compute the entire segment tree.
The time complexity of the construction is
We receive two integers
To do this we will traverse the tree and use the precomputed sums of the segments.
Let's assume that we are currently at the vertex that covers the segment
There are three possible cases:
So processing a sum query is a function that recursively calls itself once with either the left or the right child (without changing the query boundaries), or twice, once for the left and once for the right child (by splitting the query into two subqueries).
And the recursion ends whenever the boundaries of the current query segment coincides with the boundaries of the segment of the current vertex.
In that case the answer will be the precomputed value of the sum of this segment, which is stored in the tree.
Obviously we will start the traversal from the root vertex of the Segment Tree.
Example: consider the array
Let's now reason about the complexity of the algorithm.
We have to show that we can compute the sum queries in
Theorem: For each level we only visit no more than four vertices.
And since the height of the tree is
Proof: We can show that this proposition (at most four vertices each level) is true by induction.
The query works by dividing the input segment into several sub-segments for which all the sums are already precomputed and stored in the tree. And if we stop partitioning whenever the query segment coincides with the vertex segment, then we only need
Now we want to modify a specific element in the array, let's say we want to do the assignment
This query is easier than the sum query. Each level of a segment tree forms a partition of the array. Therefore an element
Thus only
It is easy to see that the update request can be implemented using a recursive function. The function gets passed the current tree vertex, and it recursively calls itself with one of the two child vertices (the one that contains
Example: given the same array as before, we want to perform the update
Segment Trees allows applying modification queries to an entire segment of contiguous elements and perform the query in the same time
When we need to update an interval we will update a node and mark its child that it needs to be updated and update it only when needed.
To every node we add a field that marks if the current node has a pending update or not.
Then, when we perform another range update or a sum query, if nodes with a pending update are involved, we first perform the updates and then solve the query.
Alternatively said, consider the following segment tree:
When there are many updates and updates are done on a range, we can postpone some updates (avoid recursive calls in update) and do those updates only when required.
Please remember that a node in segment tree stores or represents result of a query for a range of indexes.
And if this node’s range lies within the update operation range, then all descendants of the node must also be updated.
Example: consider the node with value
If our update query is for range
With Lazy propagation, we update only node with value lazy[] which represents lazy node.
The size of lazy[] is same as array that represents segment tree.
The idea is to initialize all elements of lazy[] as 0. A value 0 in lazy[i] indicates that there are no pending updates on node i in segment tree.
A non-zero value of lazy[i] means that this amount needs to be added to node i in segment tree before making any query to the node.
A persistent data structure is a data structure that remembers its previous state for each modification.
This allows to access any version of this data structure that interest us and execute a query on it.
Segment Tree is a data structure that can be turned into a persistent data structure efficiently
In fact any change request in the Segment Tree leads to a change in the data of only
So if we store the Segment Tree using pointers, then when performing the modification query we simply need to create new vertices instead of changing the available vertices.
Vertices that are not affected by the modification query can still be used by pointing to the old vertices.
Thus for a modification query
For each modification of the Segment Tree we will receive a new root vertex.
To quickly jump between two different versions of the Segment Tree, we need to store this roots in an array.
To use a specific version of the Segment Tree we simply call the query using the appropriate root vertex.
With the approach described above almost any Segment Tree can be turned into a persistent data structure.
Let's now solve nested segments with a Segment Tree and Sweep Line
Given the input array segments we compute the maximum endpoint between the segments, and call it n.
Then we create a segment tree, based on an array of length
At this point we create the array axis, which stores triples where:
segmentsisStart, which is set to true if the endpoint is the start of its segment, otherwise the end.We sort axis by the first element, the segments endpoints.
Finally we "sweep" over axis.
for `i = 0 to axis.length()axis[i].isStart == false, aka if the current endpoint is the end of its segment[segments[axis[i].index, axis[i].endpoint]res(axis[i].index, res) in the array of resultsaxis[i].index in segmentsresults by the indexes and return itWhy it works?
In words:
Consider the segments
When we find the end of a segment
Then we increase by
This works because we increase by one the start
The range sum on
An array of positive integers
Let us consider its arbitrary subarray
For every positive integer
We call the power of the subarray the sum of products
The sum contains only finite number of non-zero summands as the number of different values in the array is indeed finite.
You should calculate the power of
Besides the trivial solutions, we introduce a new algorithmic technique.
The Mo’s Algorithm is a powerful and efficient technique for solving a wide variety of range query problems.
It becomes particularly useful for kind of queries where the use of a Segment Tree or similar data structures are not feasible.
This typically occurs when the query is non-associative, meaning that the result of a query on a range cannot be derived by combining the answers of the subranges that cover the original range.
Mo’s algorithm typically achieves a time complexity of
Let's first consider an easier problem than Powerful Array
We are given an array
Additionally we are given a set of three_or_more.
The query three_or_more(l,r) aims to count the colors that occur at least three times in the subarray
A straightforward solution for the problem: simply scan the subarray and use an additional array as a counter to keep track of occurrences of each color within the range.
Whenever a color reaches three the answer is incremented by 1.
Mind that after each query we have to reset the array of counters.
Indeed, it’s evident that it has a time complexity of
The figure below illustrates an input that showcases the worst-case running time.
We have
The total length of these ranges is
Let's now see the solution using the Mo's Algorithm.
Suppose we have just answered the query for the range
Instead of starting from scratch, we can update the previous answer and counters by adding or removing the contributions of colors that are new in the query range but not in the previous one, or vice versa.
Specifically, for left endpoints, we must remove all the colors in
The same applies to right endpoints
The rust implementation below uses two closures, add and remove to keep answer and counters updated as we adjust the endpoints
pub fn three_or_more(a: &[usize], queries: &[(usize, usize)]) -> Vec<usize> {
let max = a.iter().max().unwrap()
let mut counters: Vec<usize> = vec![0; max];
let mut answers = Vec::with_capacity(queries.len());
let mut cur_l = 0;
let mut cur_r = 0; // here right endpoint is excluded
let mut answer = 0;
for &(l, r) in queries {
let mut add = |i| {
counters[a[i]] += 1;
if counters[a[i]] == 3 {
answer += 1
}
};
let mut remove = |i| {
counters[a[i]] -= 1;
if counters[a[i]] == 2 {
answer -= 1
}
};
// if the current l is bigger than the previously computed
// query then the current l has to shift to left and add the
// elements that are now relevant
while cur_l > l {
cur_l -= 1;
add(cur_l);
}
// if the current l is smaller than the previously computed
// query then it has to shift to the right and remove the
// elements that are now not relevant
while cur_l < l {
remove(cur_l);
cur_l += 1;
}
// same reasoning as before
while cur_r <= r {
add(cur_r);
cur_r += 1;
}
while cur_r > r + 1 {
cur_r -= 1;
remove(cur_r);
}
answers.push(answer);
}
answers
}
The time complexity of the algorithm remains
However we observe that a query now executes more quickly if its range significantly overlaps with the range of the previous query.
This implementation is highly sensitive to the ordering of the queries.
The previous figure becomes now a best-case for the new implementation as it takes
Mind that it is enough to modify the ordering of the above queries to revert to quadratic time (alternate between very short and very long queries).
The above considerations lead to a question: if we have a sufficient number of queries, can we rearrange them in a way that exploits the overlap between successive queries to gain an asymptotic advantage in the overall running time?
Mo's Algorithm answers positively to this question by providing a reordering of the queries such that the time complexity is reduces to
The idea is to conceptually partition the array
A query belongs to a bucket
In other terms:
Initially we group the queries based on their corresponding buckets, and within each bucket the queries are solved in ascending order of their right endpoints (aka the queries are sorted by their
The figure shows this bucketing approach and the queries of one bucket sorted by their right endpoint.
Let's analyze the complexity of the solution using this ordering
It is sufficient to count the number of times we move the indexes cur_l and cur_r. This is because both add and remove take constant time, and thus the time complexity is proportional to the overall number of moves of these two indexes.
Let's concentrate on a specific bucket.
As we process the queries in ascending order of their right endpoints, the index cur_r moves a total of at most
On the other hand, the index cur_l can both increase and decrease but it is limited within the bucket, and thus it cannot move more than
Thus, for a bucket with
Summing up over all buckets the time complexity is
Here's a Rust implementation of the reordering process.
We sort the queries by buckets, using their left endpoints, and within the same bucket we sort them in ascending order by their right endpoints.
We also have to compute a permutation to keep track of how the queries have been reordered. This permutation is essential for returning the answers to their original ordering.
pub fn mos(a: &[usize], queries: &[(usize, usize)]) -> Vec<usize> {
// Sort the queries by bucket, get the permutation induced by sorting.
// The latter is needed to permute the answers to the original ordering
let mut sorted_queries: Vec<_> = queries.iter().cloned().collect();
let mut permutation: Vec<usize> = (0..queries.len()).collect();
let sqrt_n = (a.len() as f64) as usize + 1;
sorted_queries.sort_by_key(|&(l, r)| (l / sqrt_n, r));
permutation.sort_by_key(|&i| (queries[i].0 / sqrt_n, queries[i].1));
let answers = three_or_more(a, &sorted_queries);
let mut permuted_answers = vec![0; answers.len()];
for (i, answer) in permutation.into_iter().zip(answers) {
permuted_answers[i] = answer;
}
permuted_answers
}```
## 17.1.2 Final Considerations on Mo's Algorithm
**Mo’s algorithm is an offline approach, which means we cannot use it when we are constrained to a specific order of queries or when update operations are involved.**
When implementing Mo’s algorithm, the most challenging aspect is implementing the functions `add` and `remove`.
There are query types for which these operations are not as straightforward as in previous problems and require the use of more advanced data structures than just an array of counters
## 17.1.3 - An application of Mo's Algorithm
### 17.1.3.1 - Mo's for Queries on a Tree
Consider a tree with $n$ vertices.
Each vertex has some color. Assume that the vertices are numbered from $1$ to $n$.
We represent the color of a vertex $v$ with $c_v$.
The tree root is the vertex with number $1$.
We need to answer $m$ queries.
Each query is described by two integers $v_j, k_j$.
The answer to the query is the number of colors $c$ that occurs at least $k_j$ in the subtree of vertex $v_j$.
This problem can be solved in $\Theta((m+n)\sqrt{n})$ time using the Mo's algorithm, how?
**TODO?**
## 17.2 - Solution
We can just use Mo's Algorithm and a little bit of attention in updating the answer after a `add` or a `remove`.
The solution is identical to the one seen in the previous problem, with one difference.
We are not interested anymore in the number of occurrences of $i$, denoted $K_i$, in a given subarray, but we want to compute $$\Sigma_i\ K_i^2\cdot i,\ i\in [l,r]$$
**When we increase the number of an occurrence we have to first remove the number obtained when we thought that there was one less occurrence.**
Code talks more than words:
```rust
let mut add = |i| {
// we found another occurrence of i, we remove the old "power"
sum -= counters[a[i]] * counters[a[i]] * a[i];
counters[a[i]] += 1;
// we update the power using the right number of occurreces of i
sum += counters[a[i]] * counters[a[i]] * a[i];
};
let mut remove = |i| {
sum -= counters[a[i]] * counters[a[i]] * a[i];
counters[a[i]] -= 1;
sum += counters[a[i]] * counters[a[i]] * a[i];
};```
# 18 - Longest Common Subsequence
Given two strings, `S1` and `S2`, the task is to find the length of the longest common subsequence, i.e. longest subsequence present in both strings.
**Observation:** subsequence != substring. A subsequence do not have to be contiguous.
**There are many ways to attack this problem, we use it to talk about Dynamic Programming.**
## 18.1 - Dynamic Programming
Dynamic Programming, like divide-and-conquer, solves problems by combining solutions of subproblems.
Divide-and-Conquer algorithms partitions the problem into disjoint subproblems, solve the subproblems and then combine their solutions to solve the original problem.
In contrast, **dynamic programming applies when subproblems overlap, that is, when sub-problems share sub-sub-problems.**
In this context a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common sub-sub-problems.
**A dynamic programming algorithm solves each sub-sub-problem just once and then saves its answer in a table, avoiding the work of recomputing the answer every time it solves each sub-sub-problem.**
### 18.1.2 - A first easy problem: Fibonacci
Fibonacci numbers are defined as
$$
\begin{align}
& F_0 = 0 \\
& F_1 = 1 \\
& F_n = F_{n-1} + F_{n-2}
\end{align}
$$
Our goal is to compute the n-th Fibonacci number $F_n$.
Let's consider the following trivial recursive algorithm:
```java
fibonacci(n)
if (n == 0)
return 0
if (n == 1)
return 1
return fibonacci(n-1) + fibonacci(n-2)
In computing fibonacci(n-1) we will compute fibonacci(n-2) and fibonacci(n-3),
and in computing fibonacci(n-2) we will compute fibonacci(n-3) and fibonacci(n-4) and so on.
There are lots of the same Fibonacci numbers that are computed every time from scratch.
Memorization is a trick that allows to reduce the time complexity.
Whenever we compute a Fibonacci number we store it in an array M.
Every time we need a Fibonacci number, we compute it only if the answer is not in the array.
This algorithm requires linear time and space.
fibonacciDP(n)
if (n == 0)
return 0
if (n == 1)
return 1
if (M[n] == null)
M[n] = fibonacciM(n-1) + fibonacciM(n-2)
return M[n]
There is a more direct bottom-up approach which uses linear time and constant space.
This approach typically depends on some natural notion of "size" of a sub-problem, such that solving any particular sub-problem depends only on solving "smaller" sub-problems.
We solve the subproblems by size and solve them in size order, smallest first.
When solving a particular sub-problem, we have already solved all the smaller subproblems its solution depends upon, and we have saved their solution.
In our case this approach corresponds to compute an array F which entry F[i] requires only on entries F[i-1] and F[i-2.
iteFibonacci(n)
F[n]
F[0] = 0
F[1] = 1
for i = 2 to n
F[i] = F[i-1] + F[i-2]
return F[n-1]```
### 18.1.3 Memorization vs Tabulation
Tabulation and Memorization are two common techniques used in dynamic programming to optimize the solution of problems by avoiding redundant computations and storing intermediate results.
1. **Tabulation - Bottom-Up:**
- **Definition:** **Tabulation involves solving a problem by building a table** **(usually a 2D array or matrix) and filling it in a bottom-up manner. The table is filled iteratively, starting from the base cases and moving towards the final solution.**
- **Process:**
- The tabulation approach directly computes the solution for smaller subproblems and uses these solutions to build up to the final solution.
- It is an iterative approach that avoids recursion and typically uses loops to fill in the table.
- The final result is usually found in the bottom-right cell of the table.
- **Advantages:**
- It is often more intuitive and easier to implement in an iterative manner.
- It usually has lower memory requirements since it only needs to store the necessary values in the table.
- **Disadvantages:**
- It may compute values for all subproblems, even those that are not needed for the final solution, leading to potentially higher time complexity.
2. **Memorization - Top - Down:**
- **Definition:** **Memorization involves solving a problem by storing the results of expensive function calls and returning the cached result when the same inputs occur again.**
- **Process:**
- It is a top-down approach that starts with the original problem and recursively breaks it down into smaller subproblems.
- The results of subproblems are cached (memorized) in a data structure (like a dictionary or an array).
- Before computing a subproblem, the algorithm checks whether the result is already stored in the cache. If yes, it returns the cached result; otherwise, it computes the result and stores it for future use.
- **Advantages:**
- It avoids redundant computations by storing and reusing previously computed results.
- It is often more space-efficient because it only stores results for the subproblems encountered during the actual computation.
- **Disadvantages:**
- It may introduce overhead due to function calls and the need for a cache, potentially resulting in a slightly slower runtime compared to tabulation.
In summary, both tabulation and memorization are techniques used to optimize dynamic programming solutions by avoiding redundant computations.
Tabulation builds a table bottom-up, while memorization caches results top-down.
### 18.1.4 - Rod Cutting
Serling Enterprises buys long steel rods and cuts them into shorter rods, which then sells. Each cut is free.
The management of Serling Enterprises wants to know the best way to cut up the rods.
Consider a rod of length $n$, we know that for any $i \in [1,n]$ the price of a rod of length $i$ is $p_i$.
The goal is that of determining the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.
**Solution:** **Bottom-Up Dynamic Programming**
We fill an array $r$ of size $n+1$, initialized with all zeroes, where the entry $r[i]$ stores the maximum revenue obtainable by a rod of size $i$.
Assuming we have already solved all the subproblems of size $j < i$, what's the value of $r[i]$?
**Let's list all the possibilities:**
- we do not cut, the revenue is $p_i$ (aka $p_i + r[0]$).
- we make a cut of length $1$ and we optimally cut the remaining rod of size $i-1$
- the revenue in this case is $p_i+ r[i-1]$
- we make a cut of length $2$ and we optimally cut the remaining rod of size $i-2$
- the revenue in this case is $p_2 + r[i-2]$
- ...
The value of $r[i]$ is the maximum among all these revenues.
The following pseudo-implementation clarifies the reasoning:
```java
rodCutting(rods[])
n = rods.length()
r[n+1] // intialized with all zeroes
// we inspect the rod every unit of length
for i = 1 to n
q = 0
// which is the way to cut the sub-rod of length i
// to maximize its profit?
for j = 1 to i
q = Math.max(q, p[i] + r[i-j])
r[j] = q
return r[n]
The algorithm obviously computes in
We are given a matrix
The goal is to find the minimum cost path to move from the top-left corner to the bottom-right corner (you can not move diagonally).
Solution: Bottom-Up Dynamic Programming
The idea is to fill the matrix
Said easy:
You can think of
Basically the first row and column of
Intuition: to reach
Then, to reach an "internal" cell
Basically you only have two moves:
Now that we have refreshed dynamic programming we can go back to our problem.
The subproblems here ask to compute the longest common subsequence (LCS) of prefixes of the two sequences S1 and S2: given two prefixes S1[1,i] and S2[1,j] our goal is to compute LCS(S1[1,i], S2[1,j])
Assume that we already know the solutions to the following three smaller problems
LCS(S1[1,i-1], S2[1,j-1])LCS(S1[1,i], S2[1,j-1])LCS(S1[1,i-1], S2[1,j])Then we have that
S1[i] == S2[j] we can extend a LCS of S1[1,i-1] and S2[1,j-1] by adding one character c = S1[i]S1[i] != S2[j] we can only consider LCS(S1[1,i], S2[1, j-1]) and LCS(S1[1,i-1], S2[1,j]), and we take the longer.Summarizing:
The pseudo-code of the problem is the following
longestCommonSubsequence(x, y)
n = x.length() + 1
m = y.length() + 1
dp = [n][m]
// the first row and the first column are initialized to 0
// represent the length 0 of the first or second string
for i = 0 to n
dp[i][0] = 0
for j = 0 to m
dp[0][j] = 0
for i = 1 to n
for j = 1 to m
if x[i] == y[j]
dp[i][j] = dp[i-1][j-1] + 1
else
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return dp[n-1][m-1]
In practice we create a matrix dp[n+1][m+1] where n is the length of S1 and m is the length of S2, we set the first row and column to 0 (as they represent the LCS with prefix length 0) and then iterate, using two nested loop, to check if s[i] = s[j].
In such case increase by one the previous LCS (dp[i-1][j-1]), otherwise we pick the max between the LCS of S1 without the current character and S2 without the current character.
Then we return dp[n][m], which is the LCS of S2[1..m] aka S1 and S2
Consider an array of N integers arr[].
Each element represents the maximum length of the jump that can be made forward from that element.
This means if arr[i] = x, then we can jump any distance y such that y <= x.
Find the minimum number of jumps to reach the end of the array starting from the first element.
If an element is 0, then you cannot move through that element.
Note: Return -1 if you can't reach the end of the array.
We use Dynamic Programming to solve the problem.
More specifically we use Tabulation to solve the problem:
jumps[] from left to right such that jumps[i] indicate the minimum number of jumps needed to reach the position i starting from the startjumps[]. we use two nested loops, the outer indexed with i and the inner indexed with ji = 1 to n-1 and the inner loop goes from j = 0 to ii is less than j+arr[j] then sets jumps[i] to min(jumps[i], jumps[j]+1jump[i] = INT_MAXjumps[i-1]The implementation of the solution is the following:
minNumberOfJumps(array)
n = array.le
jumps[n]
for i = 0 to n
jumps[i] = MAX
jumps[0] = 0
if n == 0 || arr[0] == 0
return -1
for i = 1 to n
for j = 0 to i
// read below
if i <= j + array[j] && jumps[j] != MAX
jumps[i] = Math.min(jumps[i], jumps[j]+1)
break
return jumps[n-1]
}```
**The key is the if guard inside the two loops:**
- `i <= j + arr[j]`: we want to reach `i` and we are in `j`. If `i <= j + array[j]` it means that `i` is reachable from `j` doing the available number of jumps in `j`, which is `array[j]`
- `jumps[j] != MAX`: we can actually reach `j` from the start
Then the minimum number of jumps required to reach `i` is the minimum between the current number of jumps to reach `i` and the number of jumps required to reach `j` plus one more jump (to reach `i`)
![[Pasted image 20240116171229.png |center| 600]]
# 20 - Partial Equal Subset Sum
Given an array `array[]` of size `N`, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.
This problem is a well-known NP-Hard problem, which admits a pseudo-polynomial time algorithm.
The problem has a solution which is almost the same as **0/1 Knapsack Problem.**
## 20.1 - 0/1 Knapsack Problem
We are given $n$ items. Each item $i$ has a value $v_i$ and a weight $w_i$.
We need to put a subset of these items in a knapsack of capacity $C$ to get the maximum total value in the knapsack.
**It is called 0/1 because each item is either selected or not selected.**
We can use the following solutions:
1) if $C$ is small we can use **Weight Dynamic Programming.** The time complexity is $\Theta(Cn)$
2) If $V = \Sigma_i\ v_i$ is small we can use **Profit Dynamic Programming.** The time complexity is $\Theta(Vn)$
3) if both $V$ and $C$ are large we can use *branch and bound*, not covered here.
**Weight Dynamic Programming**
The idea is to fill a $(n+1)\times (C+1)$ matrix $K$.
Let $K[i,A]$ be the max profit for weight $\le A$ using items from 1 up to $i$.
![[Pasted image 20240116180507.png | center | 600]]
**Profit Dynamic Programming**
The idea is similar.
We can use a $(n+1)\times (V+1)$ matrix $K$.
Let $K[V][i]$ be the minimum weight for profit at least $V$ using items from $1$ up to $i$.
Thus we have:
$$K[V][i] = \min(K[V][i-1], K[V-v[i][i-1])$$
The solution is $\max(a:K[V,n]\le C)$
## 20.2 - Solution
As in the 0/1 knapsack problem we construct a matrix $W$ with $n+1$ rows and $v+1$ columns.
Here the matrix contains booleans.
The entry $W[i][j]$ is `true` if and only if there exists a subset of the first $i$ items with sum $j$, false otherwise.
The entries of the first row $W[0][]$ are set to false, as with $0$ elements you can not make any sum.
The entries of the first column $W[][0]$ are set to true, as with the first $j$ elements you can always make a subset that has sum $0$, the empty subset.
Entry $W[i][j]$ is true either if $W[i-1][j]$ is true or $W[i-1][j - S[i]]$ is true.
- $W[i-1][j] = \text{T}$, we simply do not take the $i$-th element, and with the elements in $[1, i-1]$ we already can make a subset which sum is $j$
- $W[i-1][j-S[i]] = \text{T}$, as before: if the subset with one element less than $i$ has sum equal to $j - S[i]$ it means that if we take $i$ we reach exactly a subset with sum $j$
**Said easy:**
- we divide the sum of the array by $2$: if the sum is not divisible by $2$ it means that there cannot be two partitions that summed gives the the sum.
- once divided is the same problem above:
- exists a subset of the elements that summed gives the half of the sum?
- if yes then the answer will be true, false otherwise
```java
partialEqualSubsetSum(array)
n = array.length()
sum = 0
for i = 0 to n
sum += array[i]
if sum % 2 != 0
return false
sum = sum / 2
// dp[i][j] = true if exists a subset of the
// first i elements in array that summed gives j
dp[n+1][sum+1]
for i = 0 to n+1
dp[i][0] = true
for j = 1 to sum+1
dp[0][j] = false
// i is the current number of elements of which we make a subset
for i = 1 to n+1
// j is the current "target" sum
for j = 1 to sum+1
// if array[i-1] is alone bigger than j then it cannot be in
// the subset of elements that summed gives j
if array[i-1] > j
dp[i][j] = dp[i - 1][j]
else
dp[i][j] =
dp[i-1][j] || // dont put i in the subset
dp[i-1][j - array[i - 1]] // put i in the subset
return dp[n][sum]
The then branch of the if is crucial: if arr[i - 1] is greater than j, it means that including the current element i in the subset would make the sum exceed the current target sum j.
Therefore, the solution at dp[i][j] would be the same as the solution without including the current element, i.e., sol[i - 1][j] (aka, we do not include i, as we can't)
Given an array of integers, find the length of the longest (strictly) increasing subsequence
from the given array.
observation: subsequence, as before, it is not a contiguous.
As an example consider the sequence
The length of
In general the
Consider the sequence
Due to optimal substructure and overlapping subproblem property, we can also utilize Dynamic programming to solve the problem. Instead of memoization, we can use the nested loop to implement the recursive relation.
The outer loop will run from i = 1 to N and the inner loop will run from j = 0 to i and use the recurrence relation to solve the problem.
The reasoning is the following:
for i in 1..n) iterates over each element of the array starting from the second element.for j in 0..i) iterates over elements before the current element arr[i].arr[i] is greater than the element at index j and if increasing the length by 1 (lis[j] + 1) results in a longer LIS ending at index i. If true, it updates lis[i] accordingly.longestIncreasingSubsequence(array)
n = array.length()
lis[n]
for i = 0 to n
lis[i] = 1
for i = 1 to n
// j is used to compute the LIS of the prefix up to i
for j = 0 to i
// if the current element is bigger than the previous element
// array[j] and the lis[i] is smaller than lis[j] plus the
// current element
if array[i] > array[j] && lis[i] < lis[j] + 1
lis[i] = lis[j] + 1
return lis.max()
Said easy:
for i in 1..n) iterates over each element of the array starting from the second element.for j in 0..i) iterates over elements before the current element arr[i].array[i] is greater than the element array[j] (hence, the element at position i could be the next element of the sequence that ends at position j)array[i] is shorter than the sequence that ends in j (lis[j]) plus 1 (the maybe added element `array[i])lis[i] = lis[j] + 1The main idea of the approach is to simulate the process of finding a subsequence by maintaining a list of “buckets” where each bucket represents a valid subsequence.
Initially, we start with an empty list and iterate through the input nums vector from left to right.
For each number in nums
Consider the following pseudo-implementation
smartLIS(nums)
n = nums.length()
List ans
ans.add(nums[0])
for i = 1 to n
if nums[i] > ans.last()
ans.add(nums[i])
else
// low is the index of the smallest element >= nums[i] in `ans`
low = binarySearch(ans, nums[i])
ans.set(low, nums[i]);
return ans.length()
Said easy:
ans is the length of the current LIS.nums[i] in position low of ans.low is the index of the smallest element grater than nums[i] in ans.ans[low] with a smaller element without affecting the longest increasing subsequence, that remains valid.ans[low] with nums[i] let us "consider" a new LIS, starting from nums[i], this is because when we substitute we insert in a place that is still part of the current LIS, but if a new LIS would start entirely from the current element every element would be substituted starting from that elementIt is often useful to reduce a problem to a (single source) longest path computation on a suitable DAG (directed acyclic graph).
Let's consider again the LIS problem.
Our DAG
We use
Every vertex as an edge to
By construction exists a one-to-one correspondence between increasing subsequences of
Thus any longest path on
A longest path on a DAG
The DAG has at most
We have
The goal is to find out how many ways we can make the change of the amount
Example:
The solution is similar to the one for
We build a matrix
The following pseudo-implementation is clarifies the solution
coinChange(coins[], k) {
n = coins.length()
// store the number of ways to make change for each amount
// dp[i][j] = number of ways we can change the values j having the
// coins in coins[0..i]
// rows = coins "cut"
// column = amount, up to k
dp[n+1][k+1]
//one way to make change for amount 0, i.e., using no coins
for i = 0 to n+1
dp[i][0] = 1
for i = 1 to n+1
for j = 1 to k+1
// the current coin is itself greater than k
// we can not use it to change k
if coins[i-1] > j
dp[i][j] = dp[i-1][j]
else
// the number of ways to change j is the sum between
// 1) the number of ways without using the coin i
// 2) the number of ways using the coin i, * (see later)
dp[i][j] =
dp[i-1][j] +
dp[i][j-coins[i]]
return dp[n][amount]
* If we include the current coin, we subtract its value from the current amount j, and then consider the number of ways to make change for the reduced amount, including the current coin.
This allows for the same coin to be used multiple times, as we explore all possible combinations of coins to make change for a given amount.
Each cell in the dynamic programming table represents the number of ways to make change using a specific combination of coins.
Given an array arr[0 … n-1] containing arr[] is called bitonic if it is first increasing, then decreasing.
Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.
A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.
Solution
This problem is a slight variation of the previous problem.
Let the input array arr[] be of length n.
We need to construct two arrays lis[] and lds[] using the DP solution of the Longest Increasing Subsequence
lis[i] stores the length of the longest increasing subsequence ending in arr[i]lds[i] stores the length of the longest decreasing subsequence starting in arr[i]We return the max value of lis[i] + lds[i] -1 where
To compute lds[i] we iterate through the array backwards and apply the same reasoning used for lis[], as we are looking for a decreasing sequence but proceeding backwards, is the same as an increasing sequence.
Basically the output is the sum of the longest increasing sequence left to right and the longest increasing sequence right to left
The following is the implementation of the solution:
longestBitonicSubsequence(array)
n = array.length()
// exactly as LIS
lis[n]
for i = 0 to n
lis[i] = 1
for i = 1 to n
for j = 0 to i
if array[i] > array[j] && lis[i] < lis[j] + 1
lis[i] = lis[j] + 1
// LIS but backwards
lds[n]
for i = 0 to n
lds[i] = 1
for i = n-1 to 0
for j = n-1 to i
if array[i] > array[j] && lds[i] < lds[j] + 1 {
lds[i] = lds[j] + 1
}
lisMax = lis.max()
ldsMax = lds.max()
return lisMax + ldsMax - 1
Given a tree
An independent set is a set of nodes
Example: The nodes in red form the largest independent set of the following tree
Mind that generally the largest independent set is not unique.
Solution
Consider a bottom-up traversal of the tree.
For every node
In the case 1) ,
In the case 2)
Let
We then have the following recurrence:
Thus the problem is solved with a post-order visit of
Observation: the same problem on general graphs is NP-Hard.
There is one meeting room in a firm.
There are N meetings in the form of (start[i], end[i]) where start[i] is start time of meeting i and end[i] is finish time of meeting i.
Find the maximum number of meetings that can be accommodated in the meeting room, knowing that only one meeting can be held in the meeting room at a particular time.
Note: Start time of one chosen meeting can't be equal to the end time of the other chosen meeting.
There are various ways to solve the problem, we use it to present greedy algorithms.
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.
In many problems a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.
Example: a greedy strategy for the Travelling Salesman Problem (TSP) is the heuristic "at each step of the journey visit the nearest city".
This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps.
Note: this greedy approach is not very good on the TSP, as the current optimal choice is based on previous choices, and greedy algorithms never reconsider the choices they have made so far.
Most problems for which greedy algorithms yields good solutions (aka good approximation of the globally optimal solution) have two property:
In summary:
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
Greedy algorithms are used for optimization problems.
An optimization problem can be (optimally) solved using Greedy if the problem has the following property:
You are given
Solution:
The greedy choice is to always pick the next activity whose finish time is the least among the remaining activities and the start time is more or equal to the finish time of the previously selected activity.
The algorithm behaves as follows:
The following pseudo-implementation clarifies the reasoning:
activitySelection(activities[])
n = activities.length()
// sort by activities[i].finish component
activities.sort()
res = 1;
lastFinishTime = activities[0].finish
for i = 1 to n
// if the current activity starts after the end of the
// last selected activity then we can do it
if activities[i].start >= lastFinishTime
res++
lastFinishTime = activites[i].finish
return res
You are given an array of jobs where every job have a deadline and associated profit that can be made if the job is completed before its deadline.
It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1.
Maximize the total profit if only one job can be scheduled at a time.
Solution:
We use a greedy approach: we select first the most paying jobs and we schedule them for as late as possible (while still respecting their deadline).
Choosing the jobs with maximum profit first, by sorting the jobs in decreasing order of their profit, help to maximize the total profit as choosing the job with maximum profit for every time slot eventually maximize the total profit.
The algorithm behaves as follows:
calendar with size equal to the greatest of all the deadlines among the jobs"", the empty stringji) in calendar that is smaller than j.deadline. this is where we place j.id.calendar or use a semi-bs approachcalendar[i] = j.idres += j.profiti cannot be found simply skip the jobGiven
We want to put these items in a knapsack of capacity
In the fractional knapsack we can break items for maximizing the total value.
The greedy approach is to calculate the ratio profit/weight for each item and sort them on the basis of this ratio.
Then take the item with the highest ratio and add them as much as we can (can be whole or a fraction of it).
This will always give the maximum profit because in each step it adds an element such that this is the maximum possible profit for that much weight.
There are
For each box
You can choose some subset of boxes and rearrange them in any order you like.
Find the maximum possible number of boxes that can form a tower (the subset
Solution
TODO
Bitor has
The
Decide if Bitor can find an order of fighting that makes him defeat all monsters.
Observation: if Bitor reaches
Solution:
We have to consider at the same time the damage that a monster deals and the health it provides once killed.
This leads to considering a ratio (as in the fractional knapsack).
We consider the ratio
We then simply choose to kill monsters that make our health grows first.
The algorithm behaves as follows:
We use the greedy approach to solve the problem:
results of meetings and set a variable time_limit to the finish time of the first meetingresultstime_limit variable to the finishing time of the current meetingObservation: the problem requires only to give the maximum number of meetings that we can have in one room.
We do not care about the meetings that can be held, so results is useless.
Also we can sort the array of meetings that we have received, as there is no problem in messing their order.
In the end, we need only the variable time_limit and a variable result to increment every time we find a meeting that can happen.
The following implementation solves the problem:
meetingsInARoom(meetings)
// sort meetings by their starting time
meetings.sort()
timeLimit = meetings[0].end
// at least we held the first meeting
result = 1
for meeting in meetings
if meeting.0 > timeLimit
result++
timeLimit = meeting.end
return result;
Wilbur the pig is tinkering with arrays again.
He has the array
At one step he can choose any index
His goal is to end up with the array
Of course Wilbur wants to achieve this goal in the minimum number of steps and asks you to compute this value.
Example:
= [0,0,0,0,0][1,2,3,4,5], the target array +1 operation, one for every element ii = 0: +1 a = [1,1,1,1,1]i = 1: +1 a = [1,2,2,2,2]The solution is based upon the observation that the minimum number of operations is equal to the sum of differences (in absolute value) between consecutive elements.
Given the array
Here's the rust implementation:
wilburAndArray(array)
n = array.length()
result = Math.abs(array[0])
for i = 1 to n
result += Math.abs(array[i] - array[i-1])
return result
Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood.
She imagined the situation that is described below.
There are
Each tree has its height
Woodcutters can cut a tree and fell it to the left or to the right.
After that it occupies one of the segments
The tree trait that is not cut down occupies a single point with coordinate
Woodcutters can fell a tree if the segment to be occupied by the fallen tree does not contain any occupied point.
The woodcutters want to process as many trees as possible.
What is the maximum number of trees to fell?
We use a greedy approach to solve the problem.
The code makes it even more clear:
woodcutters(trees)
n = trees.length()
// always cut at least the first and last trees
cutted = 2
for i = 1 to n-1
// left fall: the previous tree is placed before where the
// current trees fall when "left-cutted"
if trees[i-1].x < trees[i].x - trees[i].h
cutted++
continue
// cant fall to the left, lets try to the right
// if the current tree fall in a place that is smaller
// than the next tree place, then we cut
if trees[i].x trees[i].h < trees[i+1].x
cutted++
continue
return result
}```
# 28 - Bipartite Graph
You are given an adjacency list of a graph **adj** of V of vertices having 0 based index. Check whether the graph is bipartite or not.
**The Problem in detail:**
A **Bipartite Graph** **is a graph whose vertices can be divided into two independent sets**, $U$ and $V$, such that every edge $(u, v)$ either connects a vertex from $U$ to $V$ or a vertex from $V$ to $U$.
In other words, for every edge $(u, v)$, either $u$ belongs to $U$ and $v$ to $V$, or $u$ belongs to $V$ and $v$ to $U$.
We can also say that there is no edge that connects vertices of same set.
**A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.**
## 28.1 - Graphs 101
![[Pasted image 20240222110350.png | center | 700]]
- **a)** an undirected graph $G= (V,E)$
- **b)** an adjacency-list representation of $G$
- **c)** the adjacency-matrix representation o f $G$
### 28.1.2 - Breadth-First Search
Given a graph $G = (V,E)$ and a distinguished **source** vertex $s$, BFS systematically explores the edges of $G$ to "discover" every vertex that is reachable from $s$.
It computes the distance from $s$ to each reachable vertex, where the distance to a vertex $v$ equals the smallest number of edges needed to go from $s$ to $v$.
BFS also produces a "breadth-first tree" with root $s$ that contains all reachable vertex.
For any vertex $v$ reachable from $s$, the simple path in the breadth-first tree from $s$ to $v$ corresponds to a shortest path from $s$ to $v$ in $G$ (a path containing the smallest number of edges.)
Breadth-First search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.
**You can think of it as discovering vertices in waves emanating from the source vertex.**
**Remember:** a queue is a FIFO data structure
- insert the new element as the end/tail, it "appends" elements
- remove elements at the start/head, it pop the first
```java
bfs(graph, s)
for v in graph.nodes()
if v != s
v.color = "white" // node not seen yet
v.distance = Math.MAX // maximum distance, unreachable for now
v.predecessor = null // no predecessor in the BF-Tree
s.color = "gray" // a vertex seen for the first time becomes gray
s.distance = 0 // the distance to the source is 0, we start there
s.predecessor = null // the source has no predecessor
Queue frontier
// add s as the last element of the queue
frontier.add(s)
while !frontier.isEmpty
// pop the element at the head of the frontier
u = frontier.pop()
for v in u.neighbors()
if v.color == "white"
v.color = "gray"
v.distance = u.distance + 1
v.predecessor = u
frontier.push(v)
u.color = "black" // explored all neighbors: the node becomes black
Observation:
As its name implies, DFS searches "deeper" in the graph whenever is possible.
DFS explores edges of the most recently discovered vertex
This process continues until all vertices are reachable from the original vertex have been discovered.
Unlike BFS, whose predecessor subgraph forms a tree, depth-first search produce a predecessor graph that might contains several trees, because the search may repeat form multiple sources.
Therefore we define the predecessor subgraph of a depth-first search slightly differently from that of a BFS: it always includes all vertices, and it accounts for multiple sources.
Specifically for a depth-first search the predecessor subgraph is
The edges in
Besides creating a depth first forest, DFS also timestamps each vertex.
Each vertex
dfs(graph)
for u in graph.vertices()
u.color = "white"
u.predecessor = null
global time = 0 // global variable
for u in graph.vertices()
if u.color == "white"
dfsVisit(G, u)
dfsVisit(graph, u)
time++ // time at which u has been discovered
u.d = time
for v in u.neighbors()
if v.color == "white"
v.predecessor = u
dfsVisit(G, v)
time++
u.f = time
u.color = BLACK
Observation: DFS uses a stack instead of a queue to explore the nodes. In the above implementation the stack is the activation records stack since the implementation is recursive.
An application of DFS is the decomposition of a directed graph into its strongly connected components.
A strongly connected component of a graph
The algorithm for finding strongly connected components of a graph
Given an adjacency-list representation of
Observation:
The following linear time (i.e.,
stronglyConnectedComponents(graph)
// this is to compute u.f of each node
dfs(graph)
graphT = graph.transpose()
// same as DFS but in the main loop consider the
// the vertices in order of decreasing u.f
customDFS(graphT)
// print the vertices of each tree in the depth-first forest obtained
// by customDFS as a separate strongly connected component.
printRes()
Why it works?
The idea behind this algorithm comes from a key property of the component graph
Suppose that
The vertex set
There is an edge
Looked at the other way, by contracting all edges whose incident vertices are within the same strongly connected component of
The key property is that the component graph is a DAG, which the following lemma implies.
Lemma:
Let
Then
TODO
Given a direct or undirect graph
Said differently: given a graph with weighted edges (where each edge has a non-negative weight) the goal is to find the shortest path from a specified vertex (the source) to all other vertices in the graph.
There are several algorithms to solve the problem:
TODO
A spanning tree is a subset of a graph that includes all the graph's vertices and some of the edges of the original graph, intending to have no cycles.
A spanning tree is not necessarily unique.
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.
It is a way of finding the most economical way to connect a set of vertices.
A minimum spanning tree is not necessarily unique.
All the weights of the edges in the MST must be distinct. If all the weights of the edges in the graph are the same, then any spanning tree of the graph is an MST.
The edges of the minimum spanning tree can be found using the greedy algorithm or the more sophisticated Kruskal or Prim's algorithm.
A minimum spanning tree has precisely
Kruskal's Algorithm
In Kruskal’s algorithm, sort all edges of the given graph in increasing order.
Then it keeps on adding new edges and nodes in the MST if the newly added edge does not form a cycle.
It picks the minimum weighted edge at first and the maximum weighted edge at last. Thus we can say that it makes a locally optimal choice in each step in order to find the optimal solution, aka it is a greedy algorithm.
The algorithm behaves as follows:
In a room there are
A group of friends is a group of persons where any two pair of persons are friends.
Given the list of persons that are directly friends find the number of group of friends and the number of persons in each group.
Let's see an example: consider
We can see that using the "transitive property of friendship" at the end we will have two groups of friends:
Solution:
This problem can be solved using a BFS but we use it to introduce data structures for disjoint sets.
A disjoint-set data structure is a structure that maintains a collection S1, S2, S3.. Sn of dynamic disjoint sets.
Two sets are disjoint if their intersection is null.
In a data structure of disjoint sets every set contains a representative, which is member of the set.
Consider the example above.
At the beginning there are
The next step is that
Next
And in the last step
The representative of the first group will be
How can we check if two persons are in the same group?
We use the representative elements comes in.
Let's say we want to check if
If the representative of th set that contains
We see that this is not the case, as the representative of
Some operations:
Let's define the following operations:
create-set(x) creates a new set with one element xmerge-sets(x,y) merges into one set the set that contains x and the set that contains y (x and y are in different sets), the original sets will be destroyedfind-set(x) returns the representative or a pointer to the representative of the set that contains xThen we can now solve the problem using those operations:
n = read(stdin)
for x from 1 to n
create-set(x)
for (x,y) friends
if find-set(x) != find-set(y)
merge-sets(x,y)
Now, if we want to see if two persons (x,y) are in the same group we check if find-set(x) == find-set(y)
TODO
We will analyze the running time of the disjoint-set data structure in terms of create-set(x) is called and create-set(x), merge-sets(x, y) and find-set(x) are called. Since the sets are disjoint, each time merge-sets(x, y) is called one set will be created and two will be destroyed, giving us one less set.
If there are n sets after n-1 calls of merge-sets(x,y) there will remain only one set. That’s why the number of merge-sets(x,y) calls is less than or equal to the number of create-set(x) operations.
The solution is basically an adapted version of BFS, the implementation is crystal clear.
isBipartite(graph[][], src)
// number of nodes
n = graph[0].length()
// assign the "non-color" to all the nodes
colors[n]
for i = 0 to n
colors[i] = -1
// assign a color to the src
colors[src] = 1
// fifo queue (like BFS)
Queue frontier
frontier.add(src)
while !frontier.isEmpty()
// extract a node from the queue
i = frontier.poll()
// there is a self loop: a node is connected to itself
// hence a node is the neighbor of himself, hence not bipartite
if graph[i][i] == 1
return false
for j = 0 to n
// the node i and j are neighbors
if graph[i][j] == 1
// two neighbors have the same color
if colors[i] == colors[j]
return false
// the neighbor j has no color assigned
// it is a node that we have not seen before
if color[j] == -1
color[j] = 1 - color[u]
frontier.add(j)
return true